#pragma once
#include<iostream>
using namespace std;

namespace key
{
	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* left;
		BSTNode<K>* right;

		BSTNode(const K& key)
			:_key(key)
			,left(nullptr)
			,right(nullptr)
		{}
	};

	template<class K>
	class BSTree
	{
		typedef BSTNode<K> Node;
	public:
		bool insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			
			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key);
			if (parent->_key > key)
			{
				parent->left = cur;
			}
			else
			{
				parent->right = cur;
			}

			return true;
		}

		bool find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					cur = cur->right;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

		bool erase(const K& key)
		{
			Node* parent = _root;
			Node* cur = _root;
            while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					if (cur->left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							if (parent->_key > cur->_key)
							{
								parent->left = cur->right;
							}
							else
							{
								parent->right = cur->right;
							}
						}
						delete cur;
					}
					else if (cur->right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							if (parent->_key > cur->_key)
							{
								parent->left = cur->left;
							}
							else
							{
								parent->right = cur->left;
							}
						}
						delete cur;
					}
					else
					{
						Node* minparent = cur;
						Node* minright = cur->right;
						while (minright->left)
						{
							minparent = minright;
							minright = minright->left;
						}
						cur->_key = minright->_key;

						if (minparent->left == minright)
						{
							minparent->left = minright->right;
						}
						else
						{
							minparent->right = minright->right;
						}
						delete minright;
					}
					return true;
				}
 			}
			return false;
		}

		void Inorder()
		{
			_Inorder(_root);
		}

	private:
		void _Inorder(Node* cur)
		{
			if (cur == nullptr)
			{
				return;
			}

			_Inorder(cur->left);
			cout << cur->_key << ' ';
			_Inorder(cur->right);
		}

		Node* _root = nullptr;
	};
}






namespace key_value
{
	template<class K, class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K,V>* left;
		BSTNode<K,V>* right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			, left(nullptr)
			, right(nullptr)
		{}
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTNode<K,V> Node;
	public:
		bool insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}

			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			if (parent->_key > key)
			{
				parent->left = cur;
			}
			else
			{
				parent->right = cur;
			}

			return true;
		}

		Node* find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					cur = cur->right;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		bool erase(const K& key)
		{
			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					if (cur->left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							if (parent->_key > cur->_key)
							{
								parent->left = cur->right;
							}
							else
							{
								parent->right = cur->right;
							}
						}
						delete cur;
					}
					else if (cur->right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							if (parent->_key > cur->_key)
							{
								parent->left = cur->left;
							}
							else
							{
								parent->right = cur->left;
							}
						}
						delete cur;
					}
					else
					{
						Node* minparent = cur;
						Node* minright = cur->right;
						while (minright->left)
						{
							minparent = minright;
							minright = minright->left;
						}
						cur->_key = minright->_key;

						if (minparent->left == minright)
						{
							minparent->left = minright->right;
						}
						else
						{
							minparent->right = minright->right;
						}
						delete minright;
					}
					return true;
				}
			}
			return false;
		}

		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}

	private:
		void _Inorder(Node* cur)
		{
			if (cur == nullptr)
			{
				return;
			}

			_Inorder(cur->left);
			cout << cur->_key << ':' << cur->_value << endl;
			_Inorder(cur->right);
		}

		Node* _root = nullptr;
	};
}